package ercahshu

func postorderTraversal(root *TreeNode) []int {
	ans := make([]int, 0)
	var df func(node *TreeNode)
	df = func(node *TreeNode) {
		if node == nil {
			return
		}
		df(node.Left)
		df(node.Right)
		ans = append(ans, node.Val)
	}
	df(root)
	return ans
}

func postorderTraversal1(root *TreeNode) []int {
	// 使用迭代的方式进行处理
	res := make([]int, 0)
	stk := []*TreeNode{}
	var prev *TreeNode
	for root != nil || len(stk) > 0 {
		for root != nil {
			stk = append(stk, root)
			root = root.Left
		}
		root = stk[len(stk)-1]
		stk = stk[:len(stk)-1]
		if root.Right == nil || root.Right == prev {
			res = append(res, root.Val)
			prev = root
			root = nil
		} else {
			stk = append(stk, root)
			root = root.Right
		}
	}
	return res
}
